ABC103 D - Islands War

提出

n, m = map(int, input().split())
ab = sorted([list(map(int, input().split())) for _ in range(m)])
# [s,s,s,s,s]
ans = 0
# 端と端

解答

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
# 1 2 3 4 5 6 7 8 9
# o o
# o o
# 1 2 3 4 5 6 7 8 9
# o o
# o o
# o o
# o o
# o o
ab.sort(key = lambda x:x[1])
# print(ab)
# [[1, 4], [2, 5]] -> 1
# [[3, 5], [4, 6], [2, 7], [1, 8], [7, 9]] -> 2 [7, 9]までは4を壊せば遮断できる tmpは必ず増加していく
ans = 1
# bi番目の島の左にかかる橋を壊すとして、tmp変数に壊した橋の位置を記憶
tmp = ab[0][1] - 1
for a, b in ab:
# tmpより右の位置がaだった場合は、新たに橋を壊す必要がある
# biについてソート済みなのでtmpとaを比較すれば必要性を判断することができる
if tmp < a:
ans += 1
tmp = b - 1
print(ans)

テーマ

メモ

提出

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
# 1 2 3 4 5 6 7 8 9
# o o
# o o
# 1 2 3 4 5 6 7 8 9
# o o
# o o
# o o
# o o
# o o
ab.sort()
tmpmin, tmpmax = ab[0]
ab.pop(0)
ans = 0
for a, b in ab:
if a > tmpmin:
tmpmin = a
if b < tmpmax:
tmpmax = b

Related